
/**
 * 
 * 寻找链表的中间结点
 * 
 * 题目描述

给定一个单链表 L，请编写程序输出 L 中间结点保存的数据。

如果有两个中间结点，则输出第二个中间结点保存的数据。例如：

给定 L 为 1→7→5，则输出应该为7；
给定 L 为 1→2→3→4，则输出应该为3；
输入描述
每个输入包含1个测试用例。每个测试用例：

第一行给出链表首结点的地址、结点总个数正整数 N （≤ 10^5）。

结点的地址是 5 位非负整数，NULL地址用 -1 表示。
接下来有N行，每行格式位：

Address Data Next
其中Address是结点地址，Data是该结点保存的整数数据（0 ≤ Data ≤ 10^8），Next是下一结点的地址。
输出描述
对每个测试用例，在一行中输出 L 中间结点保存的数据。

如果有两个中间结点，则输出第二个中间结点保存的数据。

备注
已确保输入的结点所构成的链表 L 不会成环，但会存在部分输入结点不属于链表 L 情况 。

用例
输入	00010 4
00000 3 -1
00010 5 12309
11451 6 00000
12309 7 11451
输出	6
说明	无
输入	10000 3
76892 7 12309
12309 5 -1
10000 1 76892
输出	7
说明	无

 * 
 */

import java.util.HashMap;
import java.util.Scanner;

/**
  * 题目解析
用例1示意图如下



链表数据结构本质上来说没有索引概念，因为其在内存上不是一段连续的内存，因此索引对于链表结构而言没有意义。

但是从使用上来说，我又经常需要去获取链表结构的第几个元素，因此大部分语言都为链表结构提高了“假索引”，比如Java的LinkedList类，虽然提高了get(index)方法，但是其底层是通过遍历链表（通过next属性找到下一个节点）来找到对应“假索引”的元素的，即LinkedList每次都需要O(n)的时间复杂度才能找到index位置上的元素。

另外，链表还有一个常考问题，那就是链表长度未知的情况下，我们如何找到链表的中间节点？

此时，就要用到快慢指针。

所谓快慢指针，即通过两个指针遍历链表，慢指针每次步进1个节点，快指针每次步进2个节点，这样快指针必然先到达链表尾部，而当快指针到达链表尾部时，慢指针其实刚好就是在链表中间节点的位置（奇数个节点取中间，偶数个取偏右边的那个值）。

本题虽然给出了节点数，但是这些节点不一定属于同一个链表结构，因此本题的链表长度也是未知的，而本题要求的链表中间节点要求刚好和快慢指针找的中间节点吻合，因此本题最佳策略是使用快慢指针。


  */
public class 寻找链表的中间结点 {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
 
        String head = sc.next();
        int n = sc.nextInt();
 
        HashMap<String, String[]> nodes = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String addr = sc.next();
            String val = sc.next();
            String nextAddr = sc.next();
            nodes.put(addr, new String[]{val, nextAddr});
        }
 
        System.out.println(solution(head, nodes));
        
    }

    public static String solution(String head, HashMap<String, String[]> nodes) {
        String[] slow = nodes.get(head);
        String[] fast = nodes.get(slow[1]);
 
        while (fast != null) {
            slow = nodes.get(slow[1]);
 
            fast = nodes.get(fast[1]);
            if (fast != null) {
                fast = nodes.get(fast[1]);
            } else {
                break;
            }
        }
 
        return slow[0];
    }
    
}
